// 1907. 【软件认证】办公室熄灯  https://oj.rnd.huawei.com/problems/1907/details
// map<Coordinate, map<int, int>> m_allDis;  // fromNode, <toNode, dis>
// timeLimit_ = min(timeLimit_, mapDistance_[N1][N2]); 小心新增
//软件攻城狮小E准备下班的时候，发现办公室只剩下他自己了，但是灯全部还开着，一方面他想关掉灯节省资源，
// 可另一方面他又得赶班车。办公室的布局可用一个正方形矩阵表示，其中：
// 0：表示空位，可以通过；
// 1：表示桌子，不可通过；
// 2：表示一盏灯（假设灯和开关一体的），可以通过；
// 3：表示小E工位（只有一个），可以通过；
// 4：表示办公室门口（只有一个），可以通过；
// 本题思路：bfs+dfs+剪枝
// 找到起点，门，灯各个之间的最短路径，基于这些最短路径，
// 回溯遍历起点，途径灯到终点门的路径，满足有限时间的最多灯数即为结果；
// 1、找到所有的坐标点，[起点，灯，门]放到一个数组里：vector allPoints;
// 2、遍历计算每个点到其他点的最短路径，路径步数放到一个二维数组里vector
// distance 2.1、计算两个点的最短路径采用bfs，每步检查是否目的点；
// 2.2、检查是否已经走过.
// 2.3、bfs往队列里新增成员时，添加完就将标记位更新.
// 3、回溯遍历二维数组vector distance：
// 3.1、回溯递归的返回条件是：当前点到达门口超出了剩余时间限制，或者无法到达门口(注意)；
// [2]
// 1. 先起点，从起点出发BFS所有能到达的节点（灯和出口），并记录节点信息
// 2. 计算两两节点间的距离，根据不同数目的对灯进行排列，
// 3.
// 计算从座位出发，经过灯排列并到达出口的时间。如果没超时限，则返回相应灯的数量。

#include <bits/stdc++.h>
using namespace std;
//#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <climits>  // LONG_MAX, INT_MAX, LONG_MAX
#include <iostream>
#include <utility>  // swap tuple
#include <vector>
using namespace std;
#define MAX_SIZE 50
//#define MAX_NODE 13
#define DIRECTION_NUM 4
#define ERR (-2)
#define INF (-1)
// space,table,light,  seat,door
enum {
  e_OUTRANGE = -1,
  e_SPACE = 0,
  e_TABLE,
  e_LIGHT,
  e_Seat,  // seat
  e_Door,  // door
};
class Solution {
  // define
  struct Coordinate {
    int x = 0, y = 0;
    // map的键的比较器
    bool operator<(Coordinate other) const {  // less{1,2,3}
      if (x == other.x) return y < other.y;
      return x < other.x;
    }
  };
  typedef tuple<int, int, int> PathNode;  // x,y, distance
  // variable
  vector<vector<int>> officeLayout_;
  int timeLimit_ = 0;
  size_t nW_ = 0;
  size_t nH_ = 0;
  set<Coordinate> stNodeLight_;  // light
  Coordinate NodeSeat_;
  Coordinate NodeDoor_;
  std::map<Coordinate, map<Coordinate, int>>
      mapDistance_;  // fromNode, <toNode, dis> 默认less
  int result_ = 0;

 public:
  // dFrom 开始到其他的全部距离,bfs
  map<Coordinate, int> getDistance(Coordinate dFrom) {
    PF("from %d,%d\n", dFrom.x, dFrom.y);
    const vector<Coordinate> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    map<Coordinate, int> retMapDist;     // toNode, distance
    queue<tuple<int, int, int>> quNode;  // x,y,distance
    set<Coordinate> stVisited;
    quNode.push({dFrom.x, dFrom.y, 0});
    stVisited.insert({dFrom.x, dFrom.y});
    while (!quNode.empty()) {
      auto [i, j, dis] = quNode.front();
      quNode.pop();
      for (auto [dx, dy] : directions) {
        int x = i + dx, y = j + dy;
        if (x < 0 || x >= nW_ || y < 0 || y >= nH_) {
          continue;
        }
        int nType = officeLayout_[x][y];
        if (nType == e_OUTRANGE || nType == e_TABLE || nType == e_Seat) {
          continue;
        }
        if (stVisited.count({x, y}) > 0) {
          continue;
        }
        if (dis + 1 > timeLimit_) {
          continue;
        }
        // out, table,   space,  seat,door,light
        if (nType == e_Door || nType == e_LIGHT) {
          retMapDist[{x, y}] = dis + 1;
          PF("=====> %d,%d\n", x, y);
        }
        stVisited.insert({x, y});
        quNode.push({x, y, dis + 1});
      }
    }
    return retMapDist;
  }
  set<Coordinate> stVisited_;
  void dfsTraval(Coordinate curPos, int timeLeft, int count) {
    if (mapDistance_[curPos].count(NodeDoor_) == 0 ||
        mapDistance_[curPos][NodeDoor_] > timeLeft) {
      return;
    }
    result_ = max(result_, count);
    if (result_ == stNodeLight_.size()) {
      return;
    }
    // 遍历全部的连接点
    for (auto [nextPos, dis] : mapDistance_[curPos]) {
      // 不是灯
      if (stNodeLight_.count(nextPos) == 0) {
        continue;
      }
      // 已走过
      if (stVisited_.count(nextPos) > 0) {
        continue;
      }
      stVisited_.insert(nextPos);
      dfsTraval(nextPos, timeLeft - dis, count + 1);
      stVisited_.erase(stVisited_.find(nextPos));
    }
  }
  int GetLightsOffNum(const int &timeLimit,
                      const vector<vector<int>> &officeLayout) {
    // init
    officeLayout_ = officeLayout;
    timeLimit_ = timeLimit;
    nH_ = officeLayout.size();
    nW_ = officeLayout[0].size();
    // push to vector, calc distance
    for (int i = 0; i < nW_; i++) {  // row
      for (int j = 0; j < nH_; j++) {
        int nBlock = officeLayout_[i][j];
        if (nBlock == e_SPACE || nBlock == e_TABLE) {
          continue;
        }
        if (nBlock == e_Seat) {
          NodeSeat_ = {i, j};
          PF("seat=%d,%d\n", i, j);
        } else if (nBlock == e_Door) {
          NodeDoor_ = {i, j};
        } else if (nBlock == e_LIGHT) {
          stNodeLight_.insert({i, j});
          PF("light=%d,%d\n", i, j);
        }
        mapDistance_[{i, j}] = getDistance({i, j});
      }
    }
    for (auto [from, mapDis] : mapDistance_) {
      for (auto [to, dis] : mapDis) {
        PF("(%d,%d)  -> (%d,%d) = %d\n", from.x, from.y, to.x, to.y, dis);
      }
    }
    if (mapDistance_[NodeSeat_].count(NodeDoor_) == 0) {  // 先判断，小心新增
      return -1;
    }
    timeLimit_ = min(timeLimit_, mapDistance_[NodeSeat_][NodeDoor_]);  //再赋值
    dfsTraval(NodeSeat_, timeLimit, 0);
    return result_;
  }
};
inline int ReadInt() {
  int number;
  cin >> number;
  return number;
}
template <typename T>
inline vector<T> ReadVector(int size) {
  vector<T> objects(size);
  for (int i = 0; i < size; ++i) {
    cin >> objects[i];
  }
  return objects;
}
int main() {
  int timeLimit;
  cin >> timeLimit;
  int row = ReadInt();
  vector<vector<int>> officeLayout;
  for (int i = 0; i < row; i++) {
    vector<int> oneRow = ReadVector<int>(row);
    officeLayout.push_back(oneRow);
  }
  Solution solu;
  int result = solu.GetLightsOffNum(timeLimit, officeLayout);
  cout << result << endl;
  return 0;
}